package array;

/**
 * Best Time to Buy and Sell Stock II
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * <p>
 * Design an algorithm to find the maximum profit.
 * You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times).
 * However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 *
 * @author Koizumi Sinya
 * @date 2018/02/09. 0:18
 * @edithor
 * @date
 */
public class Day2 {

    public static int maxProfit(int[] prices) {
        int profit = 0;

        if (prices == null || prices.length == 0) {
            return profit;
        }

        /*
            ①因为股票买入卖出，需要从第二天开始计算，所以第一天的[0]元素表示买入，需要从[1]开始计算差价
            ②将每次的差价计算出来，然后profit 通过sum运算统计所有可能的利润
            ③注意 length -1，避免角标越界
         */
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        return profit;
    }

    /**
     * Time complexity O()
     *
     * @param prices
     * @param s
     * @return
     */
    public static int bestTest1(int prices[], int s) {
        if (s >= prices.length) {
            return 0;
        }

        int max = 0;
        for (int start = s; start < prices.length; start++) {
            int maxProfit = 0;
            for (int i = start + 1; i < prices.length; i++) {
                if (prices[start] < prices[i]) {
                    int profit = bestTest1(prices, i + 1) + prices[i] - prices[start];
                    if (profit > maxProfit) {
                        maxProfit = profit;
                    }
                }
            }
            if (maxProfit > max) {
                max = maxProfit;
            }
        }
        return max;
    }
}
